package cn.z2huo.datastructure.linearlist.linkedlist;

import cn.z2huo.datastructure.linearlist.linkedlist.entity.Node;

/**
 * 合并两个线性表（链式表示），其中的元素按值非递减有序排列
 * 作者：张一卓
 * 创建日期：2020/9/26
 */
public class MergeList {
    public static void main(String[] args) {
        int[] array = {3, 5, 8, 11};
        int[] array2 = {2, 6, 8, 9, 11, 15, 20};
        Node<Integer> root = LinkedListInit.intArrayInit(array);
        Node<Integer> root2 = LinkedListInit.intArrayInit(array2);
        LinkedListUtils.printLinkedList(root);
        LinkedListUtils.printLinkedList(root2);
        LinkedListUtils.printLinkedList(merge(root, root2));
        LinkedListUtils.printLinkedList(merge2(root, root2));
    }

    /**
     * 需要新的空间，因为声明了新的结点，temp.setNext(new Node<>())
     * @param root 链表
     * @param root2 链表
     * @return 合并后链表的头结点
     */
    public static Node<Integer> merge(Node<Integer> root, Node<Integer> root2) {
        root = root.getNext();
        root2 = root2.getNext();
        Node<Integer> result = new Node<>();
        Node<Integer> temp = result;
        // 遍历两个需要合并的链表，直到遍历完结点数较少的链表
        while (root != null && root2 != null){
            temp.setNext(new Node<>());
            temp = temp.getNext();
            if (root.getData() < root2.getData()){
                temp.setData(root.getData());
                root = root.getNext();
            }else {
                temp.setData(root2.getData());
                root2 = root2.getNext();
            }
        }
        // 遍历完结点数较少的链表后，将较长的链表直接连接到结果链表之后
        temp.setNext(root != null ? root : root2);
        return result;
    }

    /**
     * 不需要新的空间，将原链表中结点之间的关系解除，重新按照元素值递减的关系将所有结点连接成新的链表
     * @param root 链表
     * @param root2 链表
     * @return 合并后链表的头结点
     */
    public static Node<Integer> merge2(Node<Integer> root, Node<Integer> root2){
        Node<Integer> result = root, temp = root;
        root = root.getNext();
        root2 = root2.getNext();
        while (root != null && root2 != null){
            if (root.getData() < root2.getData()){
                temp.setNext(root);
                temp = temp.getNext();
                root = root.getNext();
            }else {
                temp.setNext(root2);
                temp = temp.getNext();
                root2 = root2.getNext();
            }
        }
        temp.setNext(root != null ? root : root2);
        return result;
    }
}
